package com.cdream.basic.algorithm.leetcode.findElement;

import java.util.HashMap;
import java.util.Map;

/**
 *
 *
 * @author cdream
 * @date 5/30/21
 */
public class Question149 {
    public static void main(String[] args) {
        // System.out.println(new Question149().maxPoints(new int[][]{{1, 1}, {3, 2}, {5, 3}, {4, 1}, {2, 3}, {1, 4}}));
        System.out.println(new Question149().gcd(0, 1));
    }

    public int maxPoints(int[][] points) {
        // 1.以一个点为定点，计算所有与该点夹角相等的点
        // 2. 统计下数量就可以了
        int max = 1;
        for (int i = 0; i < points.length; i++) {
            Map<String, Integer> mp = new HashMap<>();
            for (int j = 0; j < points.length; j++) {
                if (i == j) {
                    continue;
                }
                int dertaX = points[i][0] - points[j][0];
                int dertaY = points[i][1] - points[j][1];

                int gcd = gcd(dertaX, dertaY);

                dertaX /= gcd;
                dertaY /= gcd;
                String key1 = dertaY + "-" + dertaX;
                mp.put(key1, mp.getOrDefault(key1, 0) + 1);
                max = Math.max(max, mp.get(key1));
            }
        }
        return max;

    }

    private int gcd(int a, int b) {
        while (b != 0) {
            int temp = a % b;
            a = b;
            b = temp;
        }
        return a;
    }



}
